{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-05-08T22:05:05.405241Z",
     "start_time": "2020-05-08T22:05:05.397090Z"
    }
   },
   "source": [
    "\n",
    "<div style=\"border:1px solid black; padding:20px 20px;text-align: justify;text-justify: inter-word\">\n",
    "    <strong>Exercise Session 5 - Path Planning_ PART 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "# Learning Goals\n",
    "\n",
    "- Understanding graph search and path planning on paper. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Path Planning in a Line-Based Map\n",
    "\n",
    "The previous exercises were done on an occupancy grid map. The grid map is already a form of graph, and the application of the Dijkstra’s algorithm or the A* algorithm is immediate.\n",
    "\n",
    "\n",
    "Please consider a line-based map and the whole process from graph generation, to path planning including metric information.\n",
    "\n",
    "\n",
    "Apply one of the algorithms seen in the course to find the best path between the start (S) and goal (G) positions of Figure below. Use only algorithms that can be processed by a computer and show clearly each step.\n",
    "\n",
    "![visibility](Images/visibility.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "____\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# EXTRA exercise on paper with different grid size and obstacles.\n",
    "## Dijkstra's Algorithm\n",
    "\n",
    "Apply the Dijkstra’s algorithm on paper on the map of the Figure below using a Manhattan distance.\n",
    "\n",
    "![Grid1](Images/grid1.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A* Algorithm\n",
    "\n",
    "Apply the A* algorithm on paper on the map of the previous exercise using a Manhattan distance from the source for the motion cost and the Manhattan distance to the goal (without obstacles) as heuristic function. The same excel file as for the previous exercice can be used here.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
